//
//  GetPermutation.swift
//  LeetCodeSummary
//
//  Created by 彭西西 on 2020/9/8.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  60. 第k个排列

import UIKit

/*
 60. 第k个排列
 给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。

 按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

 "123"
 "132"
 "213"
 "231"
 "312"
 "321"
 给定 n 和 k，返回第 k 个排列。

 说明：

 给定 n 的范围是 [1, 9]。
 给定 k 的范围是[1,  n!]。
 示例 1:

 输入: n = 3, k = 3
 输出: "213"
 示例 2:

 输入: n = 4, k = 9
 输出: "2314"
 */

class GetPermutation: NSObject {
        
    /*
     9, 206490
     
     
     假设 n = 3 ,排列组合 1,2,3   1,3,2   2,1,3   2,3,1   3,1,2   3,2,1
     
     可以发现 n 的所有排列组合一共有 n!个， 其中以 1...3 中每个数字开头的组合个数都是一样的，即 n!/n 个
     
     本题直接回溯会超时，因此我们要找到所求答案是以哪个数字开头的，再求出对应新的 k 值，这样就减少了很多不必要的运算
     
     经过上述优化，LeetCode提交可以通过，但是依旧十分耗时。达到了2872ms
    
     */
    
    var endFlage = false
    var resultArr:[[Int]] = []
    var targetHead = 0

    func getPermutation(_ n: Int, _ k: Int) -> String {
        guard n > 1 else {
            return "1"
        }
        
        var sourceArr = [Int]()
        for i in 1 ... n{
            sourceArr.append(i)
        }
        
        //将 k 分成 n 组，找到目标值在第几组
        var sum = 1
        for i in (1...n-1).reversed(){
            sum = sum*i
        }
        //以 1...n 中每个数字开头的都有有sum个
        for i in 1 ... n{
            if sum*i >= k{
                targetHead = i
                break
            }
        }
        
        print("结果以\(targetHead)开头")
        
        //求出新的 k
        let newK = k - sum*(targetHead-1)
        
        var flagArr = [Bool](repeating: false, count: n)
        flagArr[targetHead-1] = true
        self.dfs(0, [targetHead], sourceArr, flagArr, newK, targetHead)
        
        let arr = resultArr.last!
        var resultStr = ""
        for num in arr{
            resultStr += String(num)
        }
        return resultStr
    }
    
    func dfs(_ startIndex: Int, _ tmpArr: [Int], _ sourceArr: [Int], _ flagArr: [Bool], _ k: Int, _ head: Int){
        if endFlage == true {
            return
        }
        //print("\(tmpArr)")
        if tmpArr.count > 0 && tmpArr.first != targetHead {
            return
        }
        
        var tmpArr = tmpArr
        if tmpArr.count == sourceArr.count {
            resultArr.append(tmpArr)
            if resultArr.count == k {
                endFlage = true
            }
            return
        }
        var flagArr = flagArr
        for i in 0 ..< sourceArr.count{
            if flagArr[i] == false {
                tmpArr.append(sourceArr[i])
                flagArr[i] = true
                self.dfs(i+1, tmpArr, sourceArr, flagArr, k, head)
                tmpArr.removeLast()
                flagArr[i] = false
            }
        }
    }
    
    
    /*
     其实上述优化的思路可以继续往下进行，确定了第一个数字之后，可以用同样的方法求出第二位数组，然后依次往后推算

     Java官解:
     class Solution {
         public String getPermutation(int n, int k) {
             int[] factorial = new int[n];
             factorial[0] = 1;
             for (int i = 1; i < n; ++i) {
                 factorial[i] = factorial[i - 1] * i;
             }

             --k;
             StringBuffer ans = new StringBuffer();
             int[] valid = new int[n + 1];
             Arrays.fill(valid, 1);
             for (int i = 1; i <= n; ++i) {
                 int order = k / factorial[n - i] + 1;
                 for (int j = 1; j <= n; ++j) {
                     order -= valid[j];
                     if (order == 0) {
                         ans.append(j);
                         valid[j] = 0;
                         break;
                     }
                 }
                 k %= factorial[n - i];
             }
             return ans.toString();
         }
     }
     */
    
    
    //以下代码并不能输出正确答案...
    func getPermutation2(_ n: Int, _ k: Int) -> String {
        var k = k
        var factorial = [Int](repeating: 0, count: n)
        factorial[0] = 1
        for i in 1 ..< n{
            factorial[i] = factorial[i-1] * i
        }
        //[1,1,2,6,24,120,720,5040,40320]
        
        k -= k
        var string = ""
        var valid = [Int](repeating: 1, count: n+1)
        
        for i in 1...n{
            var order = k/factorial[n-i] + 1
            for j in 1...n{
                order -= valid[j]
                if order == 0 {
                    string += String(j)
                    valid[j] = 0
                    break
                }
            }
            k %= factorial[n-i]
        }
        
        return string
    }
}
